package interview.test1;

import java.util.LinkedList;

/**
 * 猴王问题 某森林有n只猴子在商量猴王选举的问题，所有的猴子都相当，大家商量了一个选举办法。
 * 所有的猴子围成一圈，先从第一个猴子开始报数，报数到13的猴子就出列。 紧接着的下一个猴子， 又从1开始进行新一轮的报数，报数到13的猴子再出列；
 * 依次重复下去， 直到原列中只剩下一个猴子为止， 这个猴子就是猴王。
 * 
 * @author alan
 *
 */
public class MonkeyKing {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int n = 100;// 猴子数
		int m = 13;// 报数
		LinkedList<Monkey> q = MonkeyKing.createMonkeys(n);
		System.out.println(q);
		System.out.println(count(n, m, q));

	}

	public static LinkedList<Monkey> createMonkeys(int n) {
		LinkedList<Monkey> q = new LinkedList<Monkey>();

		for (int i = 0; i < n; i++) {
			if (i == 0) {
				Monkey first = new Monkey(1, null);
				q.add(first);
			} else {
				Monkey t = new Monkey(i + 1, q.get(0));
				q.get(i - 1).next = t;
				q.add(t);
			}
		}

		return q;
	}

	public static Monkey count(int n, int m, LinkedList<Monkey> q) {
		int index = 0;
		int i = 0;
		while (n > 1) {
			Monkey t = q.get(i);
			index++;
			i++;
			t.index = index;
			if (t.index == m) {
				System.out.println("出局：" + t);
				q.remove(t);
				index = 0;
				n--;
				i--;
			}
			if (i == q.size()) {
				i = 0;
			}

		}

		if (q.size() == 1) {
			return q.get(0);
		}
		return null;

	}

}
